#include <stdlib.h>
#include "STACK.h"

/**
 * Program 4.5 Linked-list implementation of a pushdown stack
 * ----------------------------------------------------------
 * 采用[头指针，空的尾节点约定](https://blog.csdn.net/haoly1989/article/details/145637963)
 * 
 * 借助头指针head
 * 
 * 如何实现push操作？
 * - 在链表头插入
 * 
 * 如何实现pop操作？
 * - 在链表头删除
 * ---------------------------------------------------------
 * 
 */

typedef struct STACKnode* link;
struct STACKnode{
    Item item;
    link next;
};
static link head;

void STACKinit(int maxN){
    head = NULL;
}

int STACKempty(){
    return head == NULL;
}

void STACKpush(Item item){
    link t = malloc(sizeof(struct STACKnode));
    t->item = item;

    //请仔细体会始终在头部插入节点跟常见的在x之后插入t的区别
    link x = head;
    if (x == NULL) {
        t->next = NULL;
        head = t;
    }else {
        t->next = x;
        head = t;
    }

}

Item STACKpop(){
    Item item = head->item;
    //请仔细体会始终在头部删除节点跟常见的删除x之后的节点t的区别
    link t = head->next;
    free(head);
    head = t;
    return item;

}